# -*- coding: utf-8 -*-

import sys
import time
import math

'''

 autor: António Delgado
 Data: 11-03-2013


'''
class Quicksort:
    def __init__(self, A):
        self.A = A
        
    
    def Partition (self, A, p, r):
        x = self.A[r]
        i = p - 1
        for j in range (p, r):
            if self.A[j] <= x:
                i = i + 1
                self.A[i], self.A[j] = self.A[j], self.A[i]
        self.A[i+1], self.A[r] = self.A[r], self.A[i+1]
        return i + 1
          
    def Quicksort(self, A, p, r):
        if p < r:
            q = self.Partition(self.A, p, r)
            self.Quicksort(self.A, p, q - 1)
            self.Quicksort(self.A, q + 1, r)
         
        return self.A
        




A = [2, 1, 6, 5, 4, 7, 8, 3]
execucaoOne= time.clock()
print 'Desordenado:', A
B = Quicksort(A)
execucaoTwo= time.clock()
print 'Ordenado:', B.Quicksort(A, 0, len(A)-1)
print 'Time Inicial:', execucaoOne
print 'Time final:', execucaoTwo
print 'Time Final-Inicial:', execucaoTwo-execucaoOne


from random import uniform
from time import clock

Z = [1] + range(50, 1050, 50)
T = []
M = 25
for n in Z:
    A = [ uniform(0.0,1.0) for k in xrange(n)]
    tempos = []
    for k in range(M):
        t1 = clock()
        Quicksort(A)
        t2 = clock()
        tempos.append(t2-t1)
    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
    
    T.append((n,media, var))

X = [n for n, media, var in T]
Y = [media for n, media, var in T]
ct=15e6
Z = [n * math.log(n)/ct for n, media, var in T]

import matplotlib.pyplot as plt
plt.grid(True)
plt.ylabel(u'T(n) - tempo de execução médio em segundos')
plt.xlabel(u'n - número de elementos')
plt.plot(X,Y,'rs', label="resultado experimental")
plt.plot(X, Z, 'b^', label=u"previsão teórica")
plt.legend()
plt.show()


